package ds.tree.binarytree;

/**
 * 二叉搜索树，插入、查找、删除都很快log2(N)
 * 
 * 组织规则：所有节点的左子孙关键字都小于右子孙的关键字（这个组织规则比”堆“的组织规则要强）
 * 
 * */
public class BinaryTree {

	Node root;
	
	public BinaryTree(){}
	
	public BinaryTree(int iData){
		Node node = new Node();
		node.iData = iData;
		root = node;
	}
	
	public Node find(int key){
		Node current = root;
		while(current!=null)
		{
			if (key == current.iData ) {
				return current;
			}
			else if ( key < current.iData )
				current = current.leftChild;
			else
				current = current.rightChild;
		}
		return null;		
	}
	public boolean insert(int key){
		Node newNode = new Node();
		newNode.iData = key;
		
		if(root == null)
		{
			root = newNode;
			return true;
		}
		
		Node current = root;
		Node previous = null;
		while(current.iData != key)
		{
			previous = current;
			if(key < current.iData)
			{
				current = current.leftChild;
				if(current == null)
				{
					previous.leftChild = newNode;
					return true;
				}
			}
			else if(key > current.iData)
			{
				current = current.rightChild;
				if(current == null)
				{
					previous.rightChild = newNode;
					return true;
				}
			}
		}
		return false;
	}
	
	public Node findMin()
	{
		Node current = root;
		Node previous = null;
		while(current!=null)
		{
			previous = current;
			current = current.leftChild;
		}
		return previous;
	}
	
	public Node delete(int key)
	{
		Node current = root;
		Node previous = null;
		boolean isLeftChild = false;
		while(current != null && current.iData != key)
		{
			previous = current;
			if(key < current.iData)
			{
				current = current.leftChild;
				isLeftChild = true;
			}
			else if(key > current.iData)
			{
				current = current.rightChild;
				isLeftChild = false;
			}
		}
		// 跳出循环的话，要么没找到（current == null），要么找到了(current.iData == key)
		// 如果未找到
		if(current == null)
		{
			System.out.println("未找到");
			return null;
		}
		
		// -- 如果没有任何子节点，则不设后继 --
		if (current.leftChild == null && current.rightChild == null)
		{
			if(current == root)
				root = null;
			else if(isLeftChild)
				previous.leftChild = null;
			else
				previous.rightChild = null;
		}
		// -- 否则，如果只有左边的一个子节点，则把这个子节点作为后继 --
		else if (current.leftChild != null && current.rightChild == null) 
		{
			if(current == root)
				root = current.leftChild;
			else if(isLeftChild)
				previous.leftChild = current.leftChild;
			else
				previous.rightChild = current.leftChild;
		}
		// -- 否则，如果只有右边的一个子节点，则把这个子节点作为后继 --
		else if (current.rightChild != null && current.leftChild == null)
		{
			if(current == root)
				root = current.rightChild;
			else if(isLeftChild)
				previous.leftChild = current.rightChild;
			else
				previous.rightChild = current.rightChild;
		}
		// -- 否则，就是两个子节点都有的最复杂的情况，先找到后继，再处理 --
		else {
			// -- 找后继先和后继他爸先 --
			Node successorParent = current;
			Node successor = current.rightChild;
			while(successor.leftChild!=null)
			{
				successorParent = successor;
				successor = successor.leftChild;
			}
			// -- 如果找到的后继恰好是右子节点 --
			if(successor == current.rightChild)
			{
				successor.leftChild = current.leftChild;
				if(current == root)
					root = successor;
				else if(isLeftChild)
					previous.leftChild = successor;
				else
					previous.rightChild = successor;
			}
			// -- 否则，后继节点就是右子节点的左子后代 --
			else
			{
				successorParent.leftChild = successor.rightChild;
				successor.rightChild = current.rightChild;
				successor.leftChild = current.leftChild;
				if(current == root)
					root = successor;
				else if(isLeftChild)
					previous.leftChild = successor;
				else
					previous.rightChild = successor;
			}
		}
		return current;
	}
	
	// 找delNode的后继节点
	/*private Node getSuccessor(Node delNode)
	{
		// 根据前面的情况，node一定有rightChild
		Node previous = delNode.rightChild;
		Node current = delNode.rightChild.leftChild;
		
		while(current!=null)
		{
			previous = current;
			current = current.leftChild;
		}
		return previous;
	}*/
	
	public void inOrder(Node localRoot)
	{
		if(localRoot == null)
			return;
		inOrder(localRoot.leftChild);
		System.out.print(localRoot.iData + " ");
		inOrder(localRoot.rightChild);
	}
	
	public void preOrder(Node localRoot)
	{
		if(localRoot == null)
			return;
		System.out.print(localRoot.iData + " ");
		preOrder(localRoot.leftChild);
		preOrder(localRoot.rightChild);
	}
	
	public void postOrder(Node localRoot)
	{
		if(localRoot == null)
			return;
		postOrder(localRoot.leftChild);
		postOrder(localRoot.rightChild);
		System.out.print(localRoot.iData + " ");
	}
	
	public void setLeftSubTree(BinaryTree tree)
	{
		root.leftChild = tree.root;
	}
	
	public void setRightSubTree(BinaryTree tree)
	{
		root.rightChild = tree.root;
	}

	public Node getRoot() {
		return root;
	}
}

class BinaryTreeApp {
	public static void main(String[] args)
	{
		BinaryTree bt = new BinaryTree(50);
		bt.insert(25);
		bt.insert(75);
		bt.insert(12);
		bt.insert(38);
		bt.insert(88);
		bt.insert(63);
		
		bt.inOrder(bt.getRoot());
		
		bt.delete(50);
		
		bt.inOrder(bt.getRoot());
	}
}